# 作者: 郑驭泷
# 2025年03月21日21时59分45秒
# 2395042511@qq.com
import random
import time
import sys
sys.setrecursionlimit(10000)


class sort:
    def __init__(self, n, num_range):
        self.n = n
        self.arr = []
        self.num_range = num_range
        self.random_nums()

    def random_nums(self):
        for i in range(self.n):
            self.arr.append(random.randint(0, self.num_range - 1))

    def partition(self, left, right):
        arr = self.arr
        k = left
        for i in range(left, right):
            if arr[i] <= arr[right]:
                arr[i], arr[k] = arr[k], arr[i]
                k += 1
        arr[k], arr[right] = arr[right], arr[k]
        return k

    def quick_sort(self, left, right):
        if left < right:
            pivot = self.partition(left, right)
            self.quick_sort(left, pivot - 1)
            self.quick_sort(pivot + 1, right)

    def xiaogendui(self, parent_pos, len):
        arr = self.arr
        dad = parent_pos
        son = dad * 2 + 1
        while son < len:
            if son + 1 < len and arr[son] < arr[son + 1]:
                son = son + 1
            if arr[son] > arr[dad]:
                arr[son], arr[dad] = arr[dad], arr[son]
                dad = son
                son = dad * 2 + 1
            else:
                break


    def dagendui(self):
        arr = self.arr
        for parent_pos in range(self.n // 2 - 1,-1, -1):
            self.xiaogendui(parent_pos, self.n)
        for end_pos in range(self.n - 1, 0, -1):
            arr[end_pos], arr[0] = arr[0], arr[end_pos]
            self.xiaogendui(0, end_pos)
    def cal_time(self,sort_func,*args):
        start=time.time()
        sort_func(*args)
        end=time.time()
        return end-start
        # print(f"计算时间为{end-start}")


if __name__ == '__main__':
    s = sort(100000, 100)
    # print(s.arr)
    # s.quick_sort(0, s.n - 1)
    # s.cal_time(s.dagendui)
    print(s.cal_time(s.quick_sort,0,s.n-1))
    # print(s.arr)
